#include "avl.h"

#define ERROR 0.000001
#define Balanced(n) (n->longer < 0)

void avlRebalancePath(node path, value_t target)
{
    while (path && !(fabs(target-path->value) == 0)) {
        direction next_step = (target > path->value);
        path->longer = next_step;
        path = path->next[next_step];
    }
}

node avlRotateTwo(node *path_top, direction dir)
{
    node B, C, D, E;
    B = *path_top;
    D = B->next[dir];
    C = D->next[1-dir];
    E = D->next[dir];
    *path_top = D;
    D->next[1-dir] = B;
    B->next[dir] = C;
    B->longer = NEITHER;
    D->longer = NEITHER;
    return E;
}

node avlRotateThree(node *path_top, direction dir, direction third)
{
    node B, F, D, C, E;
    B = *path_top;
    F = B->next[dir];
    D = F->next[1-dir];

    C = D->next[1-dir];
    E = D->next[dir];
    *path_top = D;
    D->next[1-dir] = B;
    D->next[dir] = F;
    B->next[dir] = C;
    F->next[1-dir] = E;
    D->longer = NEITHER;

    B->longer = F->longer = NEITHER;

    if (third == NEITHER)
        return NULL;

    if (third == dir) {
        B->longer = 1-dir;
        return E;
    } else {
        F->longer = dir;
        return C;
    }
}


void avlRebalance(node *path_top, value_t target)
{
    node path = *path_top;
    direction first, second, third;

    if (Balanced(path)) {
        avlRebalancePath(path, target);
        return;
    }

    first = (target > path->value);

    if (path->longer != first) {
        path->longer = NEITHER;
        avlRebalancePath(path->next[first], target);
        return;
    }

    second = (target > path->next[first]->value);

    if (first == second) {
        path = avlRotateTwo(path_top, first);
        avlRebalancePath(path, target);
        return;
    }

    path = path->next[first]->next[second];
    if (target == path->value) third = NEITHER;
    else third = (target > path->value);
    
    path = avlRotateThree(path_top, first, third);
    avlRebalancePath(path, target);
}


int avlInsert(node *treep, value_t target, unsigned int setRepeated)
{
    node tree = *treep;
    node *path_top = treep;


    while (tree && !(fabs(target-tree->value) == 0)) {
        direction next_step = (target > tree->value);
        if (!Balanced(tree)) path_top = treep;
        treep = &tree->next[next_step];
        tree = *treep;
    }

    if (tree){
        tree->repeated += setRepeated;
        return 1;
    }
    
    tree = malloc(sizeof(*tree));
    tree->next[0] = tree->next[1] = NULL;
    tree->longer = NEITHER;
    tree->value = target;
    tree->repeated = setRepeated;
    *treep = tree;
    avlRebalance(path_top, target);

    return 1;
}

void avlConcate(node *tree1, node tree2, elements *el)
{
    if(tree2)
    {
        avlConcate(tree1, tree2->next[0], el);
        avlInsert(tree1, tree2->value, tree2->repeated);
        avlConcate(tree1, tree2->next[1], el);
        el->nSum += tree2->repeated;
        el->nUniq++;
    }
}

void avlShow(node n)
{
    if (n){
        avlShow(n->next[0]);
        printf("%.14f \t %i\n", n->value, n->repeated);
        avlShow(n->next[1]);
    }
}
